#include <stdlib.h>
#include <time.h>
#include <iostream>
//#include <string>

#define NUM 20

using namespace std;

int main() 
{

	int count = 5000;
	double err = 0.0;
	double eout = 0.0;
	while(count>0)
	{
		// Generate Data
		srand((unsigned) time(NULL));

		double *x = new double[NUM];
		double *y = new double[NUM];

		for(int i=0; i<NUM; i++)
		{
			x[i] = (rand() % 2000 - 1000 ) / 1000.0;
			y[i] = x[i] > 0 ? 1.0 : -1.0;
		}

		// noise
		for(int i=0; i<NUM; i++)
		{
			if(rand()%100 < 20) y[i] = -y[i];
		}

		// all possible threshold [-1, 1]
		double theta = -1.0;
		double s0 = 1.0;
		double s1 = -1.0;
		double total_err = 100000.0;
		double teout= 100000.0;
		while(theta <= 1.0)
		{
			double error0 = 0.0;
			double error1 = 0.0;
			double error2 = 0.0;

			double p = (theta+1)/2.0;

			for(int i = 0; i< NUM; i++)
			{
				double signx = x[i] - theta > 0 ? 1.0 : -1.0;
				double hx0 = signx * s0;
				if(hx0 != y[i] && signx <0)	error0 += p;
				else if(hx0 != y[i] && signx > 0) error0 += 1-p;
				double hx1 = signx * s1;
				if(hx1 != y[i] && signx <0)	error1 += p;
				else if(hx1 != y[i] && signx > 0) error1 += 1-p;
				double yn = x[i] > 0 ? 1.0 : -1.0;
				double hx2 = yn*y[i];
				if(hx2 < 0 && yn<0) error1 += p;
				else if(hx2 < 0 && yn>0) error1 += 1-p;
			}

			if(error0 < total_err)
			{
				total_err = error0;
				teout = error2;
			}

			if(error1 < total_err)
			{
				total_err = error1;
				teout = error2;
			}

			theta += 0.005;
		}

		total_err /= 20.0;
		err += total_err/5000.0;
		eout += teout;
		//cout << "total_err = " << total_err << endl;
		count--;

		delete[] x;
		delete[] y;
	}

	cout<< " err =  "<< err << " eout = "<< eout/(NUM*5000)<<endl;
	system("pause");

	return 1;
} 